﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DataTier
{
    public class PathFinder
    {

        private IList<Location> _locations;

        public PathFinder(IList<Location> locations)
        {
            _locations = locations;
        }

        public Route FindPath(Location start, Location end)
        {

            bool failed = false;

            Dictionary<Location, Route> shortestPaths = new Dictionary<Location, Route>();
            List<Location> handledLocations = new List<Location>();

            // Initialiser nye ruter (vægt = uendelig)
            InitializePaths(shortestPaths, _locations);

            // Initialiser startLocations rute (vægt = 0)
            shortestPaths[start].Cost = 0;

            // Kør igennem alle locations indtil alle er besøgte
            while (!failed && handledLocations.Count != _locations.Count)
            {

                // Sorter nuværende ruter efter laveste vægt ( = startLocation i første iteration, fordi shortestPaths[startLocation].Cost = 0)
                // Vælg den første location, der ikke er håndteret, og hvis rutes vægt er mindre end uendelig
                IList<Location> sortedLocations = GetSortedLocations(shortestPaths);
                Location locationToProcess = GetLocationToProcess(sortedLocations, handledLocations);

                // Kør igennem den valgte locations naboer
                // For hver nabo B, se om korteste rutes vægt til nabo B > kantens vægt mellem A og B + korteste rute til nabo A
                // Hvis ja, opdater rute
                if (locationToProcess != null)
                {
                    if (shortestPaths[locationToProcess].Cost != int.MaxValue)
                    {

                        IList<Connection> neighborConnections = locationToProcess.Connections;

                        foreach (Connection neighborCon in neighborConnections)
                        {
                            if (shortestPaths[neighborCon.To].Cost > neighborCon.Weight + shortestPaths[neighborCon.From].Cost)
                            {
                                shortestPaths[neighborCon.To].Connections = new List<Connection>(shortestPaths[neighborCon.From].Connections);
                                shortestPaths[neighborCon.To].Connections.Add(neighborCon);
                                shortestPaths[neighborCon.To].Cost = neighborCon.Weight + shortestPaths[neighborCon.From].Cost;
                            }
                        }

                        //Parallel.ForEach(neighborConnections, (neighborCon) =>
                        //{
                        //    if (shortestPaths[neighborCon.To].Cost > neighborCon.Weight + shortestPaths[neighborCon.From].Cost)
                        //    {
                        //        shortestPaths[neighborCon.To].Connections = new List<Connection>(shortestPaths[neighborCon.From].Connections);
                        //        shortestPaths[neighborCon.To].Connections.Add(neighborCon);
                        //        shortestPaths[neighborCon.To].Cost = neighborCon.Weight + shortestPaths[neighborCon.From].Cost;
                        //    }
                        //});

                        // Markér den valgte location som håndteret
                        handledLocations.Add(locationToProcess);

                    }
                    else
                    {
                        failed = true;
                    }
                }

            }

            return shortestPaths[end];

        }

        private void InitializePaths(Dictionary<Location, Route> paths, IList<Location> locations)
        {
            foreach (Location loc in locations)
            {
                paths.Add(loc, new Route(loc.Identifier));
            }
        }

        private int SortFunction(KeyValuePair<Location, Route> item)
        {
            return item.Value.Cost;
        }

        private IList<Location> GetSortedLocations(IDictionary<Location, Route> paths)
        {

            List<Location> sortedLocations = new List<Location>(paths.Count);
            var sortedDictionary = paths.OrderBy(SortFunction);

            foreach (var sortedItem in sortedDictionary)
            {
                sortedLocations.Add(sortedItem.Key);
            }

            return sortedLocations;

        }

        private Location GetLocationToProcess(IList<Location> sortedLocations, IList<Location> handledLocations)
        {

            Location locationToProcess = null;

            bool found = false;
            int i = 0;

            while (!found && i < sortedLocations.Count)
            {

                if (!handledLocations.Contains(sortedLocations[i]))
                {
                    locationToProcess = sortedLocations[i];
                    found = true;
                }

                i++;

            }

            return locationToProcess;

        }

    }
}
